package master;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/8/4 10:03
 */
public class M90subsetsWithDup {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
//        int[] visited = new int[nums.length];
        dfs(nums, 0, new ArrayList<Integer>());
        return res;
    }

    private void dfs(int[] nums, int start, List<Integer> list) {
        if (start == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        } else {
            res.add(new ArrayList<>(list));
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            dfs(nums, i + 1, list);
            list.remove(list.size() - 1);
        }

    }
}
